package algorithm.sorting;

import java.util.Arrays;

//希尔移位排序
public class ShellSortMove {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};

        /*int[] array = new int[8];
        for(int i=0;i<8;i++){
            array[i] = (int)(Math.random()*8000000);
        }*/

        shellSort(arr);

        System.out.println(Arrays.toString(arr));

    }
    //升序，增量减半
    public static void shellSort(int[] table){
        //,逐步缩小步长gap步长
       for(int gap = table.length/2;gap >0; gap /=2){
           for( int i=gap; i<table.length;i++){
               int j = i;
               int temp = table[j];//后面要修改，提前临时保存
               if (table[j] < table[j-gap]){
                   while ( j-gap>=0 && temp < table[j-gap] ){
                       //移动
                       table[j] = table[j-gap];
                       j -= gap;
                   }
                   //当while退出后，给temp找位置
                   table[j] = temp;
               }
           }
       }
    }
}
